package com.lun.swordtowardoffer2.c08;

import java.util.LinkedList;

import com.lun.util.BinaryTree.TreeNode;

public class ConvertBST {

	public TreeNode convertBST(TreeNode root) {
		LinkedList<TreeNode> stack = new LinkedList<>();
		TreeNode cur = root;
		int sum = 0;
		while(!stack.isEmpty() || cur != null) {
			if(cur != null) {
				stack.push(cur);
				cur = cur.right;
			}else {
				cur = stack.pop();
				cur.val = sum += cur.val;
				cur = cur.left;
			}
		}
		return root;
	}
	
}
